class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    unordered_set<string> set1;
    void dfs(vector<string>& arr,vector<int>& isVisited,vector<char>& tmp,string s){
        if(tmp.size() == isVisited.size()){//思考边界
            string t = "";
            for(char ch : tmp){
                t += ch;
                t += '-';
            }
            if(set1.find(t) == set1.end()){ // 如果集合里没有这个字符串，说明不存在重复项
                set1.insert(t);
                arr.emplace_back(tmp.begin(),tmp.end());//用参数构造
            }
            return;
        }
        for(int i=0;i<isVisited.size();i++){
            if(isVisited[i] == 0){
                isVisited[i] = 1;
                tmp.push_back(s[i]);//添加到最后一位
                dfs(arr,isVisited,tmp,s);
                tmp.pop_back();//删除最后一个元素
                isVisited[i] = 0; //恢复现场
            }
        }
    }

    vector<string> Permutation(string str) {
        // write code here
        vector<string> ans;
        int n = str.size();
        vector<int> isVisited(n,0);//如果isVisited[i] = 0 ,代表num[i]还没有被使用过
        vector<char> tmp;//最开始长度为0，存储每个排列，每找到一个合适的数就添加进去一个
        dfs(ans,isVisited,tmp,str);
        sort(ans.begin(),ans.end());
        return ans;
    }
};